package com.linchong.dynamicprogramming.test;

import com.linchong.dynamicprogramming.medium.PerfectSquare;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 7:53
 * @Description: PerfectSquares$
 * 给定一个正整数n，问最少可以将n分成几个完全平方数（1,4,9,...）之和
 * eg:13=4+9
 *
 * 1.确定状态：
 *      最后一步：
 *          最后一个最大数字j,1+...+j^2=n
 *      子问题：
 *          求(n-j^2)最小
 *      设状态f(i)=构成n的最后一个数字为i
 * 2.转移方程：
 *      f(i)=min{(n-j^2)+1|1<=j<=i}
 * 3.初始条件和边界值
 *      1<=n<=i
 *      初始条件：0被分成0个完全数之和,f(0)=0
 * 4.计算顺序：
 *      f(1),f(2),....,f(N)
 *      结果为f(N)
 *
 *
 */
public class PerfectSquares {

	 int maxNum(int n){

		int[] f = new int[n+1];
		f[0] = 0;
		for (int i = 1; i <= n; i++) {
			f[i] = Integer.MAX_VALUE;
			for (int j = 1; j*j <= i; j++) {
				if(f[i-j*j]+1<f[i]){
					f[i] = f[i-j*j]+1;
				}
			}
		}
		return f[n];
	}

	public static void main(String[] args) {
		int n = 13;
		PerfectSquares instance = new PerfectSquares();
		System.out.println(instance.maxNum(n));
	}
}
